//
// Created by Administrator on 2021/5/29.
//
#include <iostream>
#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int findBottomLeftValue(TreeNode *root) {
        //层序遍历
        queue<TreeNode *> q;
        q.push(root);
        TreeNode *levelLeft; // 每一层最左边的节点
        while (!q.empty()) {
            int levelSize = q.size();
            levelLeft = q.front();
            for (int i = 0; i < levelSize; ++i) {
                auto f = q.front();
                q.pop();
                if (f->left != nullptr) q.push(f->left);
                if (f->right != nullptr) q.push(f->right);
            }

        }
        return levelLeft->val;
    }
};

int main() {
    auto n1 = TreeNode(1), n2 = TreeNode(2), n3 = TreeNode(3), n4 = TreeNode(4),
            n5 = TreeNode(5), n6 = TreeNode(6), n7 = TreeNode(7);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n3.left = &n5;
    n3.right = &n6;
    n5.left = &n7;
    Solution sol;
    cout << sol.findBottomLeftValue(&n1) << endl;
    return 0;
}